package com.lwl.Algorithmic_data_structure.class12二叉树;

import com.lwl.Utils.MyTreeNode;

/**
 * @author lwl
 * @Description 是否平衡搜索二叉树
 * @date 2023/6/1 7:47
 */
public class Code03isBalanceSearchBinaryTree {

    static class Info {

        boolean isBST;

        int min;

        int max;

        public Info(boolean isBST, int min, int max) {
            this.isBST = isBST;
            this.min = min;
            this.max = max;
        }
    }

    public static boolean isBalanceSearchBinaryTree(MyTreeNode treeNode) {
        return process(treeNode).isBST;
    }

    public static Info process(MyTreeNode treeNode) {
        // 结束基点
        if (treeNode == null) {
            // 这里min是让右树使用，max是让左数使用的
            // 要考虑到空节点是肯定要满足下面判断条件的
            return new Info(true, Integer.MAX_VALUE, Integer.MIN_VALUE);
        }
        // 利用递归信息做判断
        Info leftInfo = process(treeNode.left);
        Info rightInfo = process(treeNode.right);

        boolean isBST = true;
        if (!leftInfo.isBST || !rightInfo.isBST || treeNode.value < leftInfo.max || treeNode.value > rightInfo.min) {
            isBST = false;
        }
        int min = leftInfo.min;
        int max = rightInfo.max;

        // 返回递归返回值
        return new Info(isBST, min, max);
    }

}
